package weka.classifiers.trees.IIDT;

import java.util.Arrays;
import java.util.Enumeration;

import weka.core.Instance;
import weka.core.Instances;
import weka.core.Attribute;
import weka.core.Utils;

public class LSID3Utils
{
	 public static final int FULL_GAIN = -1;						//Indication that attribute has full gain.
	
	 /**
	   * Computes information gain for an attribute..
	   *
	   * @param data the data for which info gain is to be computed
	   * @param att the attribute
	   * @return the information gain for the given attribute and data
	   */
	  public static double computeInfoGain(Instances data, Attribute att, double splitValue) 	     
	  {
	    double infoGain = computeEntropy(data);
	    double restEntropy = 0.0;
	    Instances[] splitData = splitData(data, att, splitValue);
	    
	    int numSubsets = 0;
	    if (att.isNominal())
	    {
	    	numSubsets = att.numValues();		    
	    }
	    else if (att.isNumeric())
	    {
	    	numSubsets = 2;
	    }
	    
	    for (int j = 0; j < numSubsets; j++) 
	    {
	      if (splitData[j].numInstances() > 0) 
	      {
	    	restEntropy +=	((double) splitData[j].numInstances() /
	                		(double) data.numInstances()) *
	                		computeEntropy(splitData[j]);
	      }
	    }
	    
	    if (restEntropy == 0)
	    {
	    	infoGain = FULL_GAIN;
	    }
	    else
	    {
		infoGain -= restEntropy;
	    }
	    
	    return infoGain;
	  }

	/**
	   * Splits a dataset according to the values of a given attribute.
	   *
	   * @param data the data which is to be split
	   * @param att the attribute to be used for splitting
	   * @return array of data subsets
	   */
	  public static Instances[] splitData(Instances data, Attribute att, double splitValue) 
	  {
		Instances[] splitData = null;
		if (att.isNominal()) 		 splitData 		= nominalSplitData(data, att);
		else if (att.isNumeric())	 splitData 		= numericSplitData(data, att, splitValue);
			    
	    for (int i = 0; i < splitData.length; i++) 
	    {
	      splitData[i].compactify();
	    }
	    
	    return splitData;
	  }
	  
	  /**
	   * Computes the entropy of a dataset.
	   * 
	   * @param data the data for which entropy is to be computed
	   * @return the entropy of the data's class distribution
	   * @throws Exception if computation fails
	   */
	  private static double computeEntropy(Instances data) 
	  {
	    double [] classCounts = new double[data.numClasses()];
	    Enumeration instEnum = data.enumerateInstances();
	    while (instEnum.hasMoreElements()) 
	    {
	      Instance inst = (Instance) instEnum.nextElement();
	      classCounts[(int) inst.classValue()]++;
	    }
	    
	    double entropy = 0.0;
	    for (int j = 0; j < data.numClasses(); j++) 
	    {
	      if (classCounts[j] > 0) 
	      {
	        entropy += (classCounts[j] / data.numInstances()) * Utils.log2(classCounts[j] / data.numInstances());
	      }
	    }
	    
	    return -entropy;
	  }
	  
	  /***
	   * Computes index of attribute based 
	   * @param infoGains
	   * @return
	   */
	  public static int computeRandomIndex(double[] infoGains)
	  {
	      int attIdx = -1;
	      for (int j = 0; j < infoGains.length; j++)
	      {
		  if (infoGains[j] == LSID3Utils.FULL_GAIN)
		  {				  
		      attIdx = j;
		  }
	      }
	      if (attIdx == -1 && isValidGains(infoGains))
	      {
		  //Convert gain values to be in (0, 1)			
		  Utils.normalize(infoGains);
		  
		  double rnd = Math.random();
		  double[] infoGainsBackup = infoGains.clone();
		  int j = 0;
		  Arrays.sort(infoGainsBackup);
		  for (j = 0; rnd > infoGainsBackup[j]
			  && j < infoGainsBackup.length - 1; j++);

		  double v = infoGainsBackup[j];

		  //Find index in original gains array.
		  //Assumption: v always exists in the infoGains.
		  attIdx = indexOf(infoGains, v);
	      }
	      else if (!isValidGains(infoGains))
	      {
		  attIdx = 0;
	      }

	      return attIdx;
	  }
	  
	  private static boolean isValidGains(double[] infoGains)
	  {
		  boolean isValidGains = false;
		  for (double d : infoGains)
		  {
			  if (d != 0.0) isValidGains = true;
		  }
		  
		  return isValidGains;
	  }
	  
	  private static int indexOf(double[] infoGains, double v)
	  {
		  int idx = -1;
		  for (int i = 0; i < infoGains.length; i++)
		  {
			  if (infoGains[i] == v)
			  {
				  idx = i;
				  break;
			  }
		  }
		  return idx;
	  }
	  
	  /***
	   * Splits data according to nominal attribute.
	   * @param data	given data
	   * @param att		given nominal attribute
	   * @return	array of data subsets
	   */
	  private static Instances[] nominalSplitData(Instances data, Attribute att)
	  {
		  Instances[] splitData = new Instances[att.numValues()];
		    
		  for (int j = 0; j < att.numValues(); j++) 
		  {
			  splitData[j] = new Instances(data, data.numInstances());
		  }
		    
		  Enumeration instEnum = data.enumerateInstances();
		    
		  while (instEnum.hasMoreElements()) 
		  {
			  Instance inst = (Instance) instEnum.nextElement();
			  splitData[(int) inst.value(att)].add(inst);
		  }
		  		  
		  return splitData;
	  }
	  
	  /***
	   * Splits data according to numeric attribute.
	   * @param data	given data
	   * @param att		given numeric attribute
	   * @return	array of two data subsets (less or equal and greater)
	   */
	  private static Instances[] numericSplitData(Instances data, Attribute att, double splitValue)
	  {
		  Instances[] splitData = new Instances[2];
		  for (int i = 0; i < splitData.length; i++) splitData[i] = new Instances(data, data.numInstances());
		  
		  Enumeration instances = data.enumerateInstances();
		  while (instances.hasMoreElements())
		  {
			  Instance instance = (Instance) instances.nextElement();
			  
			  if (instance.value(att) <= splitValue)
			  {
				  splitData[0].add(instance);
			  }
			  else
			  {
				  splitData[1].add(instance);
			  }
		  }
		  
		  return splitData;
	  }

	/**
	 * Checks whether current data set has constant values for the classifying attribute.
	 * @param data	current data set
	 * @return	true if data set has constant values for the classifying attribute, false otherwise
	 */
	public static boolean isConstClass(Instances data) 
	{
	    boolean isConstClass = true;
	    double firstClassValue = data.instance(0).value(data.classAttribute());
	    Enumeration instances = data.enumerateInstances();
	    while (instances.hasMoreElements())
	    {
		Instance instance = (Instance) instances.nextElement();

		if (instance.value(instance.classAttribute()) != firstClassValue)
		{
		    isConstClass = false;
		    break;
		}
	    }
	    return isConstClass;
	}
}